COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.turn off "{","}"
C00008 ENDMK
C⊗;
.turn off "{","}";
.cent(TORTURE NO. 1)

1. Write a function %3alt[x]%* which gives  a list whose elements are
alternate elements of the list %3x%*. 

2. Write a  unary function taking an S-expr argument %3x%* and giving
as value a list of the atoms occuring in %3x%*. 

3. Using the evaluation function of page 71 of our notes,  attempt to
evaluate a  representation of  3! (i.e. factorial  of three).   If it
doesn't work tell why. Can you fix it so it does work? 

4.Suppose  %3x%* takes  numbers as values  and %3u%*  takes as values
lists of  numbers  in ascending  order;  e.g. %3(2  4 7)%*.  Write  a
function %3merge[x;u]%* whose value is obtained from that of %3u%* by
putting %3x%* in %3u%* in  its proper place. Thus  %3merge[3;(2,4)]%*
is %3(2 3 4)%*. 

5. Using  %3merge%*,  write a  function %3sort%*  that transforms  an
unordered list of numbers into an ordered list. 

6. Write a  function to make a list without duplications of the atoms
occurring in an S-expr. 

7.Write a function to make a  list of all atoms that occur more  than
once in a given S-expr paired with their multiplicities. 

8. Write a predicate to tell  whether a given S-expr occurs more than
once in another S-expr. 

9. A pattern matcher: A pattern is an expression containing variables
which may  take on  "values" which are  subexpressions. For  example,
consider the expression  e = %3(TIMES (PLUS 3 X)  (PLUS 7 2) 3)%* and
the pattern p = %3(TIMES (PLUS VAR1 X) VAR2 VAR1).%*

This pattern, p, matches the expression if %3VAR1%* and %3VAR2%* are bound to
%33%* and %3(PLUS 7 2)%* respectively.   Define a function, %3inst[e;p;m]%* whose
value is  a table of variable-bindings (a  simple symbol table) which
when substituted into the argument  %3p%* yields the expression %3e%*.   The
argument %3m%*  is   an   initial  table   of  previously   committed
substitutions.  %3inst%* is to return  %3NO%* if the  pattern does not match,
and %3()%*  if  the pattern  (modified  by the  initial  value of  %3m%*)  is
identical to the expression.   Thus using the above examples of %3p%* and
%3e%*,  %3inst[e;p;()]%*  should  return  something  representing  %3{<VAR1:3>,
<VAR2:(PLUS  7 2)>}%*. But  (again  using %3p%*  and  %3e%* above)  
%3inst[e;p;{<VAR1:4>}]%*  returns %3NO%*.  
As  usual make the function  as abstract as
posible, separating out the representational details to subfunctions.
In dealing  with the  represntation, you  may assume  whatever naming
scheme  you wish for the  %3VAR%*s. You may assume that  no %3VAR%*s occur in
the expression,%3e%*. In fact,  if %3VAR%*s  %2do%* occur,  you have a  another
headache!    Those of  you  who are  masochistic  might examine  that
problem. 

10. Write an simple algebraic  simplifier. 
As we saw  in
the differentiation example (p. 53 of notes) the results of such
manipulation   in  symbolic  mathematics   can  lead   to  very  poor
representations.      Sophisticated   algebraic   simplifiers   are   a
necessity.  Begin the construction  of such a simplifier, keeping its
structure  as separate as possible from  the representation.  You  may
restrict attention to expressions involving variables,  integers, and
sums, products and  powers of such.  Show  your representation of the
simplification rules  and take  care to  allow easy  addition of  new
rules. 

Your rules should include such as x+0=>x, x*0=>0, x↑0=>1,... .